using UnityEngine;
using System.Collections;

/***************************************************************************************************
 * This library consists of two classes. 
 * The RandFuncs class is a collection of routines that simplify common randomisation tasks. 
 * The FastSample class is similar to the Sample function in RandFuncs, 
 * but optimised for the case where the distribution is very large or will be used very frequently.
 * 
 * Function.
 * Indices - this function is very simple. It creates an array of n elements whose values are the integers  from 0 to n - 1. Thus, the value of each element is equal to its index (ie, arr[0] == 0, arr[1] == 1, etc). This is useful in combination with the Shuffle function.
 * Rnd - generate a random float value in the range 0..1. This is used internally in the other functions. It is defined purely as a "wrapper" function, to make it easy to replace Unity's own random number generator with something else. The significance of this is that some simulation work requires the use of RNGs with specific statistical properties.
 * RndRange - generate a random integer in the range first..last-1. Similar to Rnd, this is just a wrapper for Unity's Random.Range.
 * Shuffle - this function re-orders the integer array passed to it. If the array is created with the Indices function, it can be used to create a random ordering of array indices. This could be useful for shuffling a deck of cards or questions, for example. It is also sometimes necessary to shuffle the result of the SampleRemove function.
 * Sum - this function takes an array of integers or floats and returns the sum of the values. This may be useful in its own right, but it is most likely to be used to find the total value for the Sample function.
 * Sample - choose a value at random according to the array of probabilities passed in. These probabilities are relative and need not add up to one, but the total is required. This can be passed as a parameter or, if it is omitted, the function will calculate the total itself. This function has many uses. Idle animations can be chosen with different probabilities, so that the character normally just breathes, but occasionally yawns or waves, etc. Enemies can be made to target different player characters randomly, but be more likely to attack the weakest or most important players. In general, there are many things can be chosen purely at random, but look more natural if they occur with different probabilities.
 * SampleRemove - choose a number of values from the specified range without replacement. That is to say, each value can appear in the result at most once. A typical example of the use of this function is to generate enemies randomly at spawn points, but never two of them at the same point. Note that although the results are randomly chosen, they will occur in numerical order in the array. Use the shuffle function if you need to scramble the order of the results array.
 * Dump - convert an array of integers or floats to a string representation. This is very handy for testing and debugging.
 ***************************************************************************************************/

/// <summary>
/// Create Random Data Class.
/// </summary>
public class wsRandom 
{
	/// <summary>
	/// Return an array of integers containing the numbers from zero to num - 1.
	/// </summary>
	/// <param name="num">size of array</param>
	/// <returns></returns>
	public static int[] Indices(int num) {
		int[] result = new int[num];
		
		for (int i = 0; i < result.Length; i++) {
			result[i] = i;
		}
		
		return result;
	}
	

	/// <summary>
	/// Uniform random number, 0..1 range.
	/// </summary>
	/// <returns>random float number</returns>
	public static float Rnd() {
		return Random.value;
	}
	

	/// <summary>
	/// Random integer in the range between first and last-1.
	/// </summary>
	/// <param name="first">start of range</param>
	/// <param name="last">end + 1 of range</param>
	/// <returns>random int number</returns>
	public static int RndRange(int first, int last) {
		return Random.Range(first, last);
	}

	
	/// <summary>
	/// As RndRange(int first, int last), but the start of the range is assumed to be zero.
	/// </summary>
	/// <param name="last">last</param>
	/// <returns></returns>
	public static int RndRange(int last) {
		return Random.Range(0, last);
	}


	/// <summary>
	/// Random shuffling of the supplied integer array.
	/// </summary>
	/// <param name="ints">array for shuffle</param>
	public static void Shuffle(int[] ints) {
		int temp;
		
		for (int i = 0; i < ints.Length; i++) {
			temp = ints[i];
			int swapIndex = RndRange(ints.Length);
			ints[i] = ints[swapIndex];
			ints[swapIndex] = temp;
		}
	}
	

	/// <summary>
	/// Sum of the values in the supplied integer array.
	/// </summary>
	/// <param name="ints">array for sum</param>
	/// <returns></returns>
	public static int Sum(int[] ints) {
		int result = 0;
		
		for (int i = 0; i < ints.Length; i++) {
			result += ints[i];
		}
		
		return result;
	}
	

	/// <summary>
	/// Sum of the values in the supplied float array.	
	/// </summary>
	/// <param name="floats">array for sum</param>
	/// <returns></returns>
	public static float Sum(float[] floats) {
		float result = 0f;
		
		for (int i = 0; i < floats.Length; i++) {
			result += floats[i];
		}
		
		return result;
	}
	

	/// <summary>
	/// Choose an integer at random, according to the supplied distribution.
	/// </summary>
	/// <param name="distro"></param>
	/// <param name="total"></param>
	/// <returns></returns>
	public static int Sample(float[] distro, float total) {
		float randVal = total * Rnd();
		
		for (int i = 0; i < distro.Length; i++) {
			if (randVal < distro[i]) {
				return i;
			}
			
			randVal -= distro[i];
		}
		
		return distro.Length - 1;
	}
	

	/// <summary>
	/// As Sample(float[] distro, float total), but calculate the total too.
	/// </summary>
	/// <param name="distro"></param>
	/// <returns></returns>
	public static int Sample(float[] distro) {
		float total = Sum(distro);
		return Sample(distro, total);
	}


	/// <summary>
	/// Sample several items without replacement.
	/// </summary>
	/// <param name="maxNum"></param>
	/// <param name="numSamples"></param>
	/// <returns></returns>
	public static int[] SampleRemove(int maxNum, int numSamples) {
		int[] result = new int[numSamples];
		int numNeeded = numSamples;
		
		for (int numLeft = maxNum; numLeft > 0; numLeft--) {
			float chance = (float) numNeeded / (float) numLeft;
			
			if (Rnd() < chance) {
				result[--numNeeded] = numLeft - 1;
			}
			
			if (numNeeded == 0) {
				break;
			}
		}
		
		if (numNeeded != 0) {
			result[0] = 0;
		}
		
		return result;
	}
	

	/// <summary>
	/// Make a string representation of an integer array.	
	/// </summary>
	/// <param name="ints"></param>
	/// <returns></returns>
	public static string Dump(int[] ints) {
		if (ints.Length == 0) {
			return "<Empty>";
		}
		
		string result = ints[0].ToString();
		
		for (int i = 1; i < ints.Length; i++) {
			result += ", " + ints[i].ToString();
		}
		
		return result;
	}
	

	/// <summary>
	/// Make a string representation of a float array.	
	/// </summary>
	/// <param name="floats"></param>
	/// <returns></returns>
	public static string Dump(float[] floats) {
		if (floats.Length == 0) {
			return "<Empty>";
		}
		
		string result = floats[0].ToString();
		
		for (int i = 1; i < floats.Length; i++) {
			result += ", " + floats[i].ToString();
		}
		
		return result;
	}
}

/***************************************************************************************************
 * This class implements sampling with replacement (like the Sample function in the RandFuncs class) 
 * but preprocesses the data to make the actual sampling operations very fast. 
 * The preprocessing step takes time proportional to the size of the distribution (ie, the number of options available). 
 * Once this step is complete, the samples are performed in constant time, regardless of how large the distribution is. 
 * FastSample is worth using when the distribution is large, rarely or never changes, and when many samples must be taken quickly, 
 * during a frame update, say. However, the preprocessing stage is considerably slower than a single call to RandFuncs.Sample, 
 * so FastSample is inefficient when only a few samples will be taken from the distribution.
 ***************************************************************************************************/

/// <summary>
/// Class to perform fast sampling without replacement from a distribution. This
/// has a linear time preprocessing step that is performed before sampling takes place. 
/// </summary>
public class FastSample {
	float[] distro;
	int[] aliases;
	float mean;
	
	/// <summary>
	/// Fast Sample
	/// </summary>
	/// <param name="initDistro"></param>
	public FastSample(params float[] initDistro) {
		distro = new float[initDistro.Length];
		float total = 0f;
		
		for (int i = 0; i < distro.Length; i++) {
			distro[i] = initDistro[i];
			total += distro[i];
		}
		
		Debug.Log(string.Format("Distro: {0}", wsRandom.Dump(distro)));

		
		mean = total / (float) distro.Length;
		
		Debug.Log(string.Format("Mean: {0}", mean));
		
		int[] sep = new int[distro.Length];
		
		int shortMarker = 0;
		int tallMarker = sep.Length - 1;
		
		for (int i = 0; i < distro.Length; i++) {
			if (distro[i] < mean) {
				sep[shortMarker++] = i;
			} else {
				sep[tallMarker--] = i;
			}
		}
		
		Debug.Log(string.Format("Sep: {0}", wsRandom.Dump(sep)));
		tallMarker++;
		
		Debug.Log(string.Format("Tall marker: {0}", tallMarker));

		
		aliases = new int[distro.Length];
		
		for (int i = 0; i < (sep.Length - 1); i++) {
			int curr = sep[i];
			float shortfall = mean - distro[curr];
			int firstTall = sep[tallMarker];
			distro[firstTall] -= shortfall;
			aliases[curr] = firstTall;
			
			if (distro[firstTall] < mean) {
				tallMarker++;
			}
		}
		
		aliases[sep[sep.Length - 1]] = sep[sep.Length - 1];
	}
	
	/// <summary>
	/// Next for Fast Sample
	/// </summary>
	/// <returns></returns>
	public int Next() {
		float rndVal = wsRandom.Rnd() * (float) distro.Length;
		int slotNum = Mathf.Min(Mathf.FloorToInt(rndVal), distro.Length - 1);
		float fracPart = (rndVal - (float) slotNum) * mean;
		
		if (fracPart < distro[slotNum]) {
			return slotNum;
		} else {
			return aliases[slotNum];
		}
	}
}